Search results for "Moore automata"

showing 2 items of 2 documents

Nondeterministic Moore automata and Brzozowski's minimization algorithm

2012

AbstractMoore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. We propose an algorithm that is a variant of Brzozowski’s minimization algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice. Moreover, we explore more general classes of NMA and analyze the applicability of the algorithm. For some of such classes the algorith…

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral Computer ScienceBrzozowski’s minimization algorithmSettore INF/01 - InformaticaPowerset constructionAutomata minimizationBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesTheoretical Computer ScienceNondeterministic algorithmDeterministic finite automatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonBrzozowski's minimization algorithmComputer Science::Formal Languages and Automata TheoryComputer Science(all)MathematicsNondeterministic Moore automata
researchProduct

Nondeterministic Moore Automata and Brzozowski’s Algorithm

2011

Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSettore INF/01 - InformaticaPowerset constructionBüchi automatonNonlinear Sciences::Cellular Automata and Lattice GasesNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDeterministic finite automatonDFA minimizationDeterministic automatonTwo-way deterministic finite automatonMoore automata minimization Brzozowski'algorithmNondeterministic finite automatonAlgorithmComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct